JDSL: The Data Structures Library In Java 
by Roberto Tamassia, Michael T. Goodrich, Luca Vismara, Mark Handy, Galina Shubina, Robert Cohen, Benoit Hudson, Ryan S. Baker, Natasha Gelfand, Ulrik Brandes


Listing One
package jdsl.graph.algo;

import jdsl.core.api.*;
import jdsl.core.ref.ArrayHeap;
import jdsl.core.ref.IntegerComparator;
import jdsl.graph.api.*;

public abstract class IntegerDijkstraTemplate {
// instance variables
  protected PriorityQueue pq_;
  protected InspectableGraph g_;
  protected Vertex source_;
  private final Integer ZERO = new Integer(0);
  private final Integer INFINITY = new Integer(Integer.MAX_VALUE);
  private final Object LOCATOR = new Object();
  private final Object DISTANCE = new Object();
  private final Object EDGE_TO_PARENT = new Object();

  // abstract instance methods
  protected abstract int weight (Edge e);

  // instance methods that may be overridden for special applications
  protected void shortestPathFound (Vertex v, int vDist) {
    v.set(DISTANCE,new Integer(vDist));
  }
  protected void vertexNotReachable (Vertex v) {
    v.set(DISTANCE,INFINITY);
    setEdgeToParent(v,Edge.NONE);
  }
  protected void edgeRelaxed (Vertex u, int uDist, Edge uv, int uvWeight,
                Vertex v, int vDist) { }
  protected boolean shouldContinue () {
    return true;
  }
  protected boolean isFinished (Vertex v) {
    return v.has(DISTANCE);
  }
  protected void setLocator (Vertex v, Locator vLoc) {
    v.set(LOCATOR,vLoc);
  }
  protected Locator getLocator (Vertex v) {
    return (Locator)v.get(LOCATOR);
  }
  protected void setEdgeToParent (Vertex v, Edge vEdge) {
    v.set(EDGE_TO_PARENT,vEdge);
  }
  protected EdgeIterator incidentEdges (Vertex v) {
    return g_.incidentEdges(v,EdgeDirection.OUT | EdgeDirection.UNDIR);
  }
  protected Vertex destination (Vertex origin, Edge e) {
    return g_.opposite(origin,e);
  }
  protected VertexIterator vertices () {
    return g_.vertices();
  }
  protected PriorityQueue newPQ () {
    return new ArrayHeap(new IntegerComparator());
  }

  // output instance methods
  public final boolean isReachable (Vertex v) {
    return v == source_
      || v.has(EDGE_TO_PARENT) && v.get(EDGE_TO_PARENT) != Edge.NONE;
  }
  public final int distance (Vertex v) throws InvalidQueryException {
    try {
      return ((Integer)v.get(DISTANCE)).intValue();
    }
    catch (InvalidAttributeException iae) {
      throw new InvalidQueryException(v+" has not been reached yet");
    }
  }
  public Edge getEdgeToParent (Vertex v) throws InvalidQueryException {
    try {
      return (Edge)v.get(EDGE_TO_PARENT);
    }
    catch (InvalidAttributeException iae) {
      String s = (v == source_) ? " is the source vertex"
     : " has not been reached yet";
      throw new InvalidQueryException(v+s);
    }
  }

  // instance methods composing the core of the algorithm
  public void init (InspectableGraph g, Vertex source) {
    g_ = g;
    source_ = source;
    pq_ = newPQ();
    VertexIterator vi = vertices();
    while (vi.hasNext()) {
      Vertex u = vi.nextVertex();
      Integer uKey = (u == source_) ? ZERO : INFINITY;
      Locator uLoc = pq_.insert(uKey,u);
      setLocator(u,uLoc);
    }
  }
  protected final void runUntil () {
    while (!pq_.isEmpty() && shouldContinue())
      doOneIteration();
  }
  public final void doOneIteration () throws InvalidEdgeException {
    Integer minKey = (Integer)pq_.min().key();
    // remove a vertex with minimum distance from the source
    Vertex u = (Vertex)pq_.removeMin();
    if (minKey == INFINITY)
      vertexNotReachable(u);
    else {   // the general case
      int uDist = minKey.intValue();
      shortestPathFound(u,uDist);
      int maxEdgeWeight = INFINITY.intValue()-uDist-1;
      EdgeIterator ei = incidentEdges(u);
      while (ei.hasNext()) {   // examine all the edges incident with u
     Edge uv = ei.nextEdge();
     int uvWeight = weight(uv);
     if (uvWeight < 0 || uvWeight > maxEdgeWeight)
       throw new InvalidEdgeException
         ("The weight of "+uv+" is either negative or causing overflow");
     Vertex v = destination(u,uv);
     Locator vLoc = getLocator(v);
     if (pq_.contains(vLoc)) {   // v is not finished yet
       int vDist = ((Integer)vLoc.key()).intValue();
       int vDistViaUV = uDist+uvWeight;
       if (vDistViaUV < vDist) {   // relax
         pq_.replaceKey(vLoc,new Integer(vDistViaUV));
         setEdgeToParent(v,uv);
       }
       edgeRelaxed(u,uDist,uv,uvWeight,v,vDist);
     }
      }
    }
  }
  public final void execute (InspectableGraph g, Vertex source) {
    init(g,source);
    runUntil();
  }
  public void cleanup () {
    VertexIterator vi = vertices();
    while (vi.hasNext()) {
      vi.nextVertex().destroy(LOCATOR);
      try {
     vi.vertex().destroy(EDGE_TO_PARENT);
     vi.vertex().destroy(DISTANCE);
      }
      catch (InvalidAttributeException iae) { }
    }
  }

}   // class IntegerDijkstraTemplate


Listing Two
package jdsl.graph.algo;

import jdsl.core.api.*;
import jdsl.core.ref.NodeSequence;
import jdsl.graph.api.*;
import jdsl.graph.ref.EdgeIteratorAdapter;

public abstract class IntegerDijkstraPathfinder
  extends IntegerDijkstraTemplate {

  // instance variables
  private Vertex dest_;

  // overridden instance methods from IntegerDijkstraTemplate
  protected boolean shouldContinue () {
    return !isFinished(dest_);
  }

  // output instance methods
  public boolean pathExists () {
    return isFinished(dest_);
  }
  public EdgeIterator reportPath () throws InvalidQueryException {
    if (!pathExists())
      throw new InvalidQueryException
     ("No path exists between "+source_+" and "+dest_);
    else {
      Sequence retval = new NodeSequence();
      Vertex currVertex = dest_;
      while (currVertex != source_) {
     Edge currEdge = getEdgeToParent(currVertex);
     retval.insertFirst(currEdge);
     currVertex = g_.opposite(currVertex,currEdge);
      }
      return new EdgeIteratorAdapter(retval.elements());
    }
  }

  // instance methods
  public final void execute (InspectableGraph g, Vertex source, Vertex dest) {
    dest_ = dest;
    init(g,source);
    if (source_ != dest_)
      runUntil();
  }

}   // class IntegerDijkstraPathfinder


Listing Three
import jdsl.graph.api.*;
import jdsl.graph.algo.IntegerDijkstraPathfinder;
import support.*;

public class FlightDijkstra extends IntegerDijkstraPathfinder {

  // instance variables
  private int startTime_;

  // overridden instance methods from IntegerDijkstraPathfinder
  protected int weight (Edge e) {
    // the flightspecs for the flight along edge e
    FlightSpecs eFS = (FlightSpecs)e.element();
    int connectingTime = TimeTable.diff(eFS.departureTime(),
                                        startTime_+distance(g_.origin(e)));
    return connectingTime+eFS.flightDuration();
  }
  protected EdgeIterator incidentEdges (Vertex v) {
    return g_.incidentEdges(v,EdgeDirection.OUT);
  }

  // instance methods
  public void execute (InspectableGraph g, Vertex source, Vertex dest,
                       int startTime) {
    startTime_ = startTime;
    super.execute(g,source,dest);
  }

}   // class FlightDijkstra